Матч 242, Разбиение команды (TeamSplit)

Дивизион 2, Уровень 1

Имеется несколько людей, которых необходимо разбить на две команды. Каждый человек обладает силой, которая хранится в массиве strengths. Выбираются два капитана, которые начинают набирать людей себе в команду. Капитаны делают свой выбор по очереди, при этом естественно выбирая себе игрока с наибольшей силой. Когда все игроки будут разбиты по командам, процесс деления игроков заканчивается. Сила команды равна суммарной силе всех ее игроков. Необходимо вычислить абсолютное значение разности сил полученных двух команд.

Класс: TeamSplit

Метод: int difference(vector<int> strengths)

Ограничения: массив strengths содержит от 1 до 50 чисел, 1 £ strengths[i] £ 1000.

Вход. Массив strengths, содержащий силы игроков.

Выход. Абсолютное значение разности сил полученных двух команд.

Пример входа

strengths

{5,7,8,4,2}

{100}

{9,8,7,6}

{1,5,10,1,5,10}

Пример выхода

4

100

2

0

РЕШЕНИЕ

сортировка + жадный алгоритм

Отсортируем участников игры по возрастанию их силы. Первый капитан берет самого сильного игрока, второй – самого сильного из оставшихся. И так далее по очереди. Для нахождения разности сил команд достаточно найти разницу суммы сил игроков, стоящих на нечетных позициях (в отсортированном массиве) и сил игроков на четных позициях. Результатом будет модуль вычисленной разности.

ПРОГРАММА

#include <cstdio>

#include <cmath>

#include <vector>

#include <algorithm>

using namespace std;

class TeamSplit

{

public:

int difference(vector<int> strengths)

{

int i, res = 0;

sort(strengths.begin(),strengths.end());

for(i = 0; i < strengths.size(); i++)

if (i % 2) res += strengths[i]; else res -= strengths[i];

return abs(res);

}

};